/* 
*哈希表 拉链法 
*/  
#include<stdio.h>  
#include<stdlib.h>  
  
#define MinTableSize 10  
  
typedef int ElemType;  
typedef unsigned int Index;  
  
typedef struct ListNode  
{  
    ElemType element;  
    struct  ListNode *next;  
}*Position;  
  
typedef Position List;  
  
/* List *TheList will be an array of lists, allocated later */  
/* The lists use headers (for simplicity), */  
/* though this wastes space */  
typedef struct HashTbl  
{  
    int TableSize;  
     List *TheLists;  
}*HashTable;  
  
int NextPrime(int N)  
{  
    int i;  
  
    if(N%2==0)  
        N++;  
    for(;;N+=2)  
    {  
        for(i=3;i*i<=N;i+=2)  
            if(N%i==0)  
                return 0;  
        return N;     
    }  
}  
  
/*Hash function for ints*/  
Index Hash(ElemType Key,int TableSize)  
{  
    return Key%TableSize;  
}  
  
HashTable InitializeTable(int TableSize)  
{  
    HashTable H;  
    int i;  
  
    if(TableSize<MinTableSize)  
    {  
        printf("Table size too small!\n");  
        return NULL;  
    }  
      
    /*Allocate table*/  
    H=(HashTable)malloc(sizeof(struct HashTbl));  
    if(NULL==H)  
      printf("Out of space!!!\n");  
  
    H->TableSize=NextPrime(TableSize);  
      
    /*Allocate array of lists*/  
    H->TheLists=(List *)malloc(sizeof(List)*H->TableSize);  
    if(NULL==H->TheLists)  
    {  
      printf("Out of space!!!\n");  
      free(H);  
      return NULL;  
    }  
    /*Allocate list  headers*/  
    for(i=0;i<H->TableSize;i++)  
    {  
        H->TheLists[i]=(Position)malloc(sizeof(struct ListNode));  
        if(NULL==H->TheLists[i])  
            printf("Out of space!!!\n");  
        else  
            H->TheLists[i]->next=NULL;  
  
        H->TheLists[i]->element=0;//哈希表中所有元素的key初始化为0  
    }  
  
    return H;  
}  
  
Position Find(ElemType Key,HashTable H)  
{  
    Position p;  
    List L;  
  
    L=H->TheLists[Hash(Key,H->TableSize)];  
    p=L->next;  
    while(p!=NULL&&p->element!=Key)/*Probably need strcmp!!*/  
        p=p->next;  
  
    return p;  
}  
  
void Insert(ElemType Key,HashTable H)  
{  
    Position pos,newCell;  
    List L;  
  
    pos=Find(Key,H);  
    if(NULL==pos)/*Key is not found*/  
    {  
        newCell=(Position)malloc(sizeof(struct ListNode));  
        if(NULL==newCell)  
          printf("Out of space!!!");      
        else  
        {  
            L=H->TheLists[Hash(Key,H->TableSize)];  
            newCell->next=L->next;  
            newCell->element=Key;/*Probably need strcpy*/  
            L->next=newCell;  
        }  
    }  
}  
  
void DestroyTable(HashTable H)  
{  
    int i;  
  
    for(i=0;i<H->TableSize;i++)  
    {  
        Position p=H->TheLists[i];  
        Position temp;  
  
        while(p!=NULL)  
        {  
            temp=p->next;  
            free(p);  
            p=temp;  
        }  
    }  
    free(H->TheLists);  
    free(H);  
}  
  
void printHash(HashTable H,int len)  
{  
    int i;  
    for(i=0;i<len;i++)  
    {  
        Position p=H->TheLists[i];  
        while(p)  
        {  
            printf("address=%d value=%d\n",i,p->element);  
            p=p->next;  
        }     
    }  
  
}  
int main()  
{  
      
    HashTable H;  
    Position p=NULL;  
    int array[]={19,14,23,01,68,20,84,27,55,11,10,79};  
    int len=sizeof(array)/sizeof(array[0]);  
    int i;  
    ElemType k;  
               
    H=InitializeTable(len);  
    for(i=0;i<len;i++)  
    {  
        Insert(array[i],H);   
    }  
    printHash(H,len);  
    printf("\n\n");  
      
    printf("please input the value which need find:");  
    scanf("%d",&k);  
    p=Find(k,H);  
    if(p)  
      printf("%d",p->element);  
    else  
      printf("cannot find the value!");  
    printf("\n\n");  
       
    printf("free the table\n");  
    DestroyTable(H);  
    printf("it's done!!!");  
    printf("\n\n");  
  
    return 0;  
}  